import java.util.*;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<Integer, Integer> idx = new HashMap<>(n); // 预分配空间
        for (int i = 0; i < n; i++) {
            idx.put(nums1[i], i);
        }
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            int x = nums2[i];
            while (!st.isEmpty() && x >= st.peek()) {
                // 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」
                st.pop();
            }
            if (!st.isEmpty() && idx.containsKey(x)) { // x 在 nums1 中
                ans[idx.get(x)] = st.peek(); // 记录答案
            }
            st.push(x);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        int[] result = solution.nextGreaterElement(nums1, nums2);
        System.out.println("结果：");
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}
